连通图

Time Limit: 20 Sec Memory Limit: 512 MB

Description

给定一个连通的无向图和若干个小集合,每个小集合包含一些边。对于每个集合，你需要确定将集合中的边从原来的无向图中删除后该图是否保持连通。
一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。

Input

输入的第一行包含两个整数n和m(l≤n≤10000,1≤m≤100000)，表示无向图的点数和边数，每个点从1到n标号。

接下来的m行表示图的每条边，每行包含两个整数a和b——一条边连接的两个端点的标号。保证每对顶点最多被一条边连接。

没有一条边连接两个相同的顶点。

每条边按照输入的顺序标号为1到m。
接下来的一行包含一个整数k(1≤k≤100000)，表示需要测试的小集合的个数。

接下来的k行每行描述一个小集合。

每行的第一个数c(1≤c≤4)表示集合中边的个数,接下来有c个整数表示集合中边的标号,保证集合中的整数互不相同。

Output

输出k行,每行对应一个小集合的测试结果。

第i行包含“Connected”（没有引号)，如果给定的图去掉对应的集合中的边仍然连通，否则应该包含一个“Disconnected”。

Sample Input

4 5
　1 2
　2 3
　3 4
　4 1
　2 4
　3
　1 5
　2 2 3
　2 1 2

Sample Output

Connected
　Disconnected
　Connected

HINT

N<=100000 M<=200000 K<=100000

Main idea

给定一张无向联通图，询问删除掉若干条边后图是否联通，多次询问。

Solution

首先我们看到删边判联通，第一反应想到了LCT，由于图不是一棵树，无法用LCT实现，那么我们否决掉了动态维护的方法。
　　根据可以离线询问这一特征来思考如何操作，发现k(询问数)<=100000，显然是log级别的做法，结合可离线的特征，这时候只剩下了对于所有询问一起进行操作的方法，现在我们得出了算法：CDQ分治。
　　发现直接删边操作较为困难，我们逆向思维，考虑如何在一个空的图上加边。
　　先考虑只有两个询问的情况，假定我们的询问删边集合为A,B，那么显然想到了先把不在A中并且不在B中边加入（这时称其为状态一），然后分开处理，先加入不在A中但是在B中的边，判下是否联通就得到了A中的答案，然后回到状态一，加入不在B中在A中的边，判断一下得到了B的答案。
　　然后基于这样的整个思路，我们考虑如何将两个集合拓展到多个集合。
　　立马想到了分治，对于所有集合分治使其类同于A,B两种“大集合”，然后继续分治，最后必然可以归于仅有两个小集合的情况，然后向上回溯即可。加边用并查集加入即可。
　　我们来整理一下CDQ分治的思路：
　　　　1、加入不在左区间但在右区间的边；
　　　　2、对于左区间继续分治；
　　　　3、回到上一层的状态（在分治的时候记录并查集中改变了的父子关系，暴力修改回去即可）
　　　　4、加入不在右区间但在左区间的边；
　　　　5、对于右区间继续分治；
　　　　……
　　最后判断是否联通的时候又发现一开始的整张图是处于连通状态的，所以我们只要判断删掉的边的端点是否连通即可。

Code

#include<bits/stdc++.h>
using namespace std;

const int ONE=200005;

int n,m,Bian;
int fat[ONE],cnt;
int PD[ONE];
int Ans[ONE];

struct power
{
    int x,y;
}a[ONE*2],q[ONE*100];

struct point
{
    int c;
    int b[5];
}quey[ONE];

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Find(int x)
{
    if(x!=fat[x])
    {
        q[++cnt].x=x;   q[cnt].y=fat[x];
        fat[x]=Find(fat[x]);
    }
    return fat[x];
}

void Un(int x,int y)
{
    int f1=Find(x);
    int f2=Find(y);
    if(f1!=f2)
    {
        q[++cnt].x=f2;  q[cnt].y=fat[f2];
        fat[f2]=f1;
    }
}

int Get_pd(int l)
{
    int pd=1;
    for(int i=1;i<=quey[l].c;i++)
    {
        int j=quey[l].b[i];
        if(Find(a[j].x) != Find(a[j].y))
        {
            pd=0;
            break;
        }
    }
    return pd;
}

void Mark(int l,int r,int t)
{
    for(int i=l;i<=r;i++)
    {
        for(int j=1;j<=quey[i].c;j++)
            PD[quey[i].b[j]]=t;
    }
}

void Add(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        for(int j=1;j<=quey[i].c;j++)
        {
            int num=quey[i].b[j];
            if(PD[num]) continue;
            Un(a[num].x,a[num].y);
        }
    }
}

void Back(int Now_cnt)
{
    for(;cnt>Now_cnt;cnt--)
        fat[q[cnt].x]=q[cnt].y;
}

void CDQ(int l,int r)
{
    if(l==r)
    {
        Ans[l]=Get_pd(l);
        return;
    }

    int Now_cnt=cnt;
    int mid=(l+r)/2;
    Mark(l,mid,1); Add(mid+1,r); Mark(l,mid,0);
    CDQ(l,mid);

    Back(Now_cnt);
    Mark(mid+1,r,1); Add(l,mid); Mark(mid+1,r,0);
    CDQ(mid+1,r);
}


int main()
{
    n=get();    Bian=get();
    for(int i=1;i<=n;i++) fat[i]=i;
    for(int i=1;i<=Bian;i++)
    {
        a[i].x=get();   a[i].y=get();
    }

    m=get();
    for(int i=1;i<=m;i++)
    {
        quey[i].c=get();
        for(int j=1;j<=quey[i].c;j++)
            quey[i].b[j]=get();
    }

    Mark(1,m,1);
    for(int i=1;i<=Bian;i++)
    {
        if(PD[i]) continue;
        Un(a[i].x,a[i].y);
    }
    Mark(1,m,0); cnt=0;

    CDQ(1,m);

    for(int i=1;i<=m;i++)
    {
        if(Ans[i]) printf("Connected");
        else printf("Disconnected");
        printf("\n");
    }
}